COMMENT ⊗   VALID 00015 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.require "memo.pub[let,jmc]" source
C00004 00003	#. Creativity
C00016 00004	#. %3Generality%1
C00017 00005	#. %3Pattern matching and higher order patterns%1
C00018 00006	#. %3Learning from experience%1
C00019 00007	#. %3Tree search%1
C00020 00008	#. %3The frame problem%1
C00021 00009	#. %3 The qualification problem and minimal reasoning%1
C00022 00010	#. %3Vagueness and fuzziness%1
C00023 00011	#. %3Causality and ability%1
C00024 00012	#. %3Objects and substances in space and time%1
C00025 00013	#. %3Self-consciousness%1
C00026 00014	#. %3Motivational structure%1
C00028 00015	.skip 1
C00029 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.turn off "{"
.cb PROBLEMS OF ARTIFICIAL INTELLIGENCE


.ITEM←0

#. Creativity

	Machines will never be able to compete with humans intellectually
until they exhibit something comparable to human creativity.  However,
all the literature dealing with creativity that I know about takes
a rather mystical attitude and doesn't seriously try to analyze
creativity - just admire it.  Admiration is fine, but won't result
in computer programs.

	Our first strategy is to seek what might be called
"easy creativity" rather than immediately try to duplicate Einstein
or Shakespeare.  To this end we tentatively define creativity as
the introduction of concepts into the solution of a problem that
are not involved in the statement of the problem or in the common
sense knowledge immediately called forth by the statement of the
problem.
My favorite example of easy creativity is the following
"checkerboard covering problem":

	"Two diagonally opposite corner squares are removed from
an 8 by 8 checkerboard.  The problem is whether the board can
be covered with dominoes, each dominoe being a 1 by 2 rectangle
capable of covering two adjacent squares".

	The classical proof that the board cannot be covered requires
noticing that a dominoe covers two squares of opposite color, but
since the deleted squares are of the same color, there remain 32
squares of one color to be covered and only 30 of the opposite color.

	Our idea is that this proof is creative, because it involves
introducing an idea not apparently relevant to the statement of
the problem - namely, the colors of the squares.  To a literate
combinatorial mathematician, the problem is easy, because parity
arguments are common in combinatorial problems, and he will quickly
begin to look for such an argument.  Nevertheless, I want to call
the proof creative - even if an experienced combinatorist may not
get many creativity points for suggesting it.  Getting computer
programs that will come up with this proof without too much
adhockery won't be easy, and I think the effort will provide a
beginning at deeper forms of creativity.

	Here is a related problem that can be solved by similar
methods.  "Prove that a 3 by 3 by 3 cube cannnot be traversed by
a path that goes through faces of the subcubes, visits each subcube
exactly once, and ends in the middle subcube".  Some like to regard
it as a problem of a worm eating its way through a barrel of 27
apples arranged in a cubical way.  This one involves some creativity
even for someone who knows the solution of the checkerboard problem.

	Three other solutions of the checkerboard problem have some
interest.  Shmuel Winograd of IBM's Thomas J. Watson Research Center
proposed the following "non-creative" solution.  The number of vertical
dominoes projecting from the first row into the second must be odd,
since one square is missing and a horizontal dominoe takes up an
even number of squares.  Likewise the number projecting from the
second row to the third must be odd, and so forth down to the
number of dominoes projecting from the seventh row to the eighth.
Therefore, the total number of vertical dominoes is the sum of
seven odd summands and therefore must be odd.  By a similar argument,
the number of horizontal dominoes must be odd.  Thus the total
number of dominoes is the sum of two odd numbers and must be
even.  But this number is 31.  In spite of Winograd's contention,
I think this proof must be regarded as creative, because it involves
introducing new ways of adding up the number of dominoes.

	Marvin Minsky of the M.I.T. Artificial Intelligence
Laboratory proposed a different proof based on dividing the
board into parallel diagonals starting with a diagonal containing
two squares adjacent to one of the deleted squares.  Clearly two
dominoes project from the 2-square diagonal to the 3-diagonal.  So
one projects from the 3-diagonal to the 4-diagonal, hence 3 
project from the 4-diagonal to the 5-diagonal, 2 from 5 to 6,
4 from 6 to 7, and 3 from 7 to 8.  Starting at the opposite
corner we also get 3 from 7 to 8, covering only six squares of
the 8-diagonal.  Minsky's proof gets more non-creativity points,
because it applies only to the 8 by 8 checkerboard, and one could
wonder whether it would also work for a 10 by 10 board, whereas
the standard proof and Winograd's proof obviously extend to
any boards with an even number of squares on an edge.  Actually
Minsky's argument can be generalized to an arbitrary board, and,
if we like, we can regard the generalization as a metamathematical
argument that the Minsky technique will give a special proof for
any size board.

	The next class of proofs is due to D. Stefanyuk of the
Institute of Information Transmission Problems in Moscow.
Stefanyuk starts by labelling an arbitrary square on the board
with the number 1, labelling its neighbors 2, labelling their
neighbors 3, etc.  We then note that one dominoe projects from
the 1-square into the 2-squares.  How many project from 2-squares
to 3-squares depends on where we are in relation to the edge and
corners of the board, but for any initial square it can be figured
out.  Proceeding from 2-squares to 3-squares, etc., we can hope
to arrive at a contradiction at the end.  Experience shows that
we always do arrive at a contradiction, so that Stefanyuk has
found a whole family of proofs that the mutilated checkerboard
can't be covered.  However, he hasn't proved that the method
will always work, although everyone believes it will always
work.

	Stefanyuk's proofs and Minsky's proof have a common
generalization.  Namely, take any set of squares
all of the same color, label them 1, and continue as before.
Namely, count the number that must project from 1-squares to
2-squares, and hope to arrive at a contradiction.  Stefanyuk
starts from an arbitrary single square and Minsky starts from
the four squares adjacent to the deleted squares.

	We can show that these proofs will always work by going
back to a color argument.  Since we start with squares of a
the 1-squares are of a single color, the 2-squares will be of
the opposite color, etc.  Therefore, a dominoe can never be
placed within the %2n%1-squares for any particular %2n%1.
(If the 1-squares aren't of one color, this can happen).
Now count the %2n%1-squares for odd %2n%1, and the %2n%1-squares
for even %2n%1 separately.  Each group consists of all the squares of
one color, and therefore one group has 32 squares and the
other 30.  But if the numbers of dominoes projecting from the
%2n%1-squares to the %2n+1%1-squares were to work out, the numbers
of squares of each color would have to be the same.
It is tempting to ask whether the method can be further generalized
to include the Winograd proof.

	The purpose, besides entertainment, of presenting all these
proofs is to provide food for thought concerning the problem of
making computers creative.  It appears possible though very
difficult to make a computer program that would come up with all
these proofs.  Since no one of these mathematicians found all of
them, it would be a substantial achievement.  My intuition is that
such a program would tell us something more about creativity.


#. %3Generality%1

#. %3Pattern matching and higher order patterns%1

#. %3Learning from experience%1

#. %3Tree search%1
#. %3The frame problem%1
#. %3 The qualification problem and minimal reasoning%1
#. %3Vagueness and fuzziness%1
#. %3Causality and ability%1
#. %3Objects and substances in space and time%1
#. %3Self-consciousness%1

	What must an intelligent program know about itself and its
mental states
and mental processes?  How does it relate to what humans know about
their own mental states and processes?
#. %3Motivational structure%1

	What motivational structures shall we give our programs,
and how do these relate to the motivational structures of humans.
I will argue that the motivational structures of humans are not
related merely to problem solving ability, and it will not be
to our advantage to construct intelligent computer programs
with human-like motivational structures.  They mightn't be obedient,
and we might be motivated to ascribe to them rights and duties.

	We can immediately mention two characteristics of human
motivation that we won't want machines to have.  First, our ideas
of what are worthwhile lifetime goals are affected by our immediate
chemical state.  In particular, fatigue affects long term goal
structure.

	Second, in humans subgoals often acquire a force independent
of the goals that gave rise to them.  Thus behavioral psychology suggests
that goals are adopted to secure parental approval.  However, such
goals often are pursued even when they lead to subsequent parental
disapproval.
.skip 1
.begin verbatim
John McCarthy
Artificial Intelligence Laboratory
Computer Science Department
Stanford University
Stanford, California 94305

ARPANET: MCCARTHY@SU-AI
.end

.turn on "{"
%7This draft of
PROBLE.AI[S77,JMC]
PUBbed at {time} on {date}.%1